﻿#pragma once

/*自己实现快速排序代码
* 思路：D&C 找基准点，分区，递归
*/

#include "../Base/CommTool.h"

namespace QuickSort
{
	class Solution
	{
	public:
		void quick_sort(vector<int>& src)
		{
			if (src.size() <= 1)
				return;

			partial_sort(src, 0, src.size() - 1);
		}


	private:
		//分区，返回pivot的index
		int partial(vector<int>& src,  int index_b, int index_e)
		{
			int pivot = src[index_b];
			int curr = index_b + 1;
			int tail = index_e;
			while (curr <= tail) //为什么要小于等于的条件，因为是先移动后比较的，最后一个移动完了，但是尚未比较
			{
				if (src[curr] > pivot)
				{
					std::swap(src[curr], src[tail--]);
				}
				else
				{
					++curr;
				}
			}
			std::swap(src[index_b], src[--curr]);

			return curr;
		}

		void partial_sort(vector<int>& src, int index_b, int index_e)
		{
			if ( index_b >= index_e)
				return;
		
			int pIndex = partial(src, index_b, index_e);
			partial_sort(src, index_b, pIndex - 1);
			partial_sort(src, pIndex + 1, index_e);
		}

		
	};

	void Test()
	{
		Solution solv;
		vector<int> src{
			7,4,62,1,4,3,9,8,2,6
		};

		solv.quick_sort(src);
		PrintVector(src);
	}

}
